COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00006 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a24.tex[106,phy] \today\hfill}

\bigskip\noindent
{\rmn
{\narrower\smallskip\noindent
{\bf Exercise.} [Search]

\noindent
The numbers were made by elves who live in Numeraguay. On Day~1, they
invented~1. Since then, every day they have combined in all possible
ways, by $+$, $-$, $\times$, and~$/$, the numbers they had by the end
of the previous day. For example, on Day~2 they made:
$$\eqalignno{2&=1+1\cr
0&=1-1\cr
\noalign{\smallskip\hbox{\hskip20pt{On Day 3 they made}}\smallskip}
3&=1+2\cr
4&=2+2\cr
-1&=0-1\cr
-2&=0-2\cr
1/2&=1/2\cr}$$
On Day 4 they got 5, 6, 7, 8, 1/3, 2/3, 4/3, 3/2, and some more negative
numbers. On what day did they get 22/7 and 34/55?
What numbers were combined to get them? To keep it simple, assume they
didn't keep any numbers with numerator or denominator greater than~100.

\bigskip
\noindent{\bf Solution:}

\noindent
Use three boolean arrays, {\tt ANYDAY}, {\tt YESTERDAY}, and 
{\tt TODAY}, of type\break
{\tt ARRAY(-100..100,0..100) OF BOOLEAN}. {\tt ANYDAY$[i,j]$} is true if
$i/j$ has been made.\break 
{\tt YESTERDAY$[i,j]$} is true if $i/j$ 
was first made on the previous day. {\tt TODAY$[i,j]$} is true if 
$i/j$ has been made on current day.
For each day, iterate over~$i$ and~$j$ (with {\tt ANYDAY$[i,j]$} true),
$k$~and $m$ (with {\tt YESTERDAY$[k,m]$} true). Form the numbers $i/j\pm k/m$,
$(i/j)\times (k/m)$, $(i/j)/(k/m)$, etc. After simplification, if not
in {\tt ANYDAY}, store them in {\tt TODAY}. At the end of each day, copy
{\tt TODAY} into {\tt ANYDAY} and {\tt YESTERDAY}. Watch for $22/7$ and $34/55$.
\smallskip}
}


\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd;
First draft September 10, 1984

\bye